Many important cryptosystems, such as RSA, use modular as well as non-modular arithmetic, including exponentiation and multiplication, with large modulus values. The classical method of calculating a non-modular product involves partitioning the operands into blocks or “digits” and applying a weighted sum over cross-products of the digits. This naïve multiplication approach, however, is computationally expensive in many practical cases.
For modular multiplication, e.g., in cryptographic computations, it is common practice to use an efficient method, known as Montgomery modular multiplication (or simply Montgomery multiplication). To perform Montgomery multiplication, the operands are converted to a special Montgomery form using an algorithm known as Montgomery reduction. Multiplication of the operands in Montgomery form avoids the need for modular reduction as required in conventional arithmetic (although a simpler conditional reduction is still required if the resulting product is greater than the modulus). The Montgomery reduction and multiplication algorithms are described, for example, by Menezes et al., in the Handbook of Applied Cryptography (1996), section 14.3.2, pages 600-603, whose disclosure is incorporated herein by reference.
Cryptosystems may be subject to various types of attacks aimed to expose internal secret information. In an attack referred to as a side-channel attack (SCA) secret information can be deduced by analyzing the power consumption behavior during execution of an underlying cryptographic function. For example, Amiel et al., describe in an article entitled “Power Analysis for Secret Recovering and Reverse Engineering of Public Key Algorithms,” proceedings of the 14th international conference on selected areas in cryptography, SAC 2007, LNCS, volume 4876, pages 110-125, Springer, Heidelberg, whose disclosure is incorporated herein by reference, differential power analysis (DPA) attacks, applied to non-modular multiplication computations.